package 其他;
/*
 *@Author: helen
 *@Date:   2021/8/6 21:14
 *@Description:
     网上看的题目，是多益网络的校招算法笔试题。我也要投简历给多益了，所以就在网上看了看多益以前的面试题。
    这道题意思是给定一个大于 5 的数 x，这个数与 3、4 有如下关系：
    x = 3 * n + 4 * m，
    其中 6 = 3 * 2 + 4 * 0
    7 = 3 * 1 + 4 * 1
    8 = 3 * 0 + 4 * 2
    9 = 3 * 3 + 4 * 0
    题目解析：
    可得出
    10 = 6 + 4 = 7 + 3
    11 = 7 + 4 = 8 + 3
    12 = 8 + 4 = 9 + 3
    13 = 10 + 3 = 9 + 4
    14 = 10 + 4 = 11 + 3
    …
    可见从 x > 9 开始，就可以写成 基本数（6、7、8、9）的形式 + 4 * n 或者 3 * M。
    有一个很简单的思路就是不断的用给定的数 x 去减 3 或者 4，然后记录次数。当减3的次数多了就减4，
    减4的次数多了就减3，最后总能减到基本数（6、7、8、9）。
    算法实现采用递归，时间复杂度为 O（n）。
 */


import java.util.HashMap;
import java.util.Scanner;

public class test08 {
    public static int result = Integer.MIN_VALUE;
    public static void solution(int n, int n3, int n4){
        if(n < 10){
            switch (n){
                case 6: n3 += 2;break;
                case 7: break;
                case 8: n4 += 2;break;
                case 9: n3 += 3;break;
            }
            result = Math.abs(n3 - n4);
            return ;
        }
        if (n3 >= n4){
            solution(n - 4, n3, n4 + 1);
        }else {
            solution(n - 3, n3 + 1, n4);
        }
    }

    public static void main(String[] args) {
        HashMap<String,String> hashMap = new HashMap<>();
        while (true) {
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            solution(n, 0, 0);
            System.out.println("最小值为：" + result);
        }
    }

}
